package leetcode331周赛;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/5 14:54
 */
public class leetcode打家劫舍4 {



    /*
     最优解是 二分 答案 :

     最大化最小值, 最小化最大值, 要想到 用 二分答案:( 这是 一个套路!)
     当然 二分 不出来的 时候,也可以 考虑 一手 动态规划!


     */





    // 内存 溢出!
    public int solution(int k,int nums[]){
        int dp[][] = new int[nums.length + 1][k + 1];
        return recursion(0,k,nums,dp);
    }
    public int recursion(int index,int k,int nums[],int dp[][]){
        if(index >= nums.length){
            return k == 0 ? 0 : Integer.MAX_VALUE;
        }
        // 判断 k <= 0 的这个 basecase
        if(dp[index][k] != 0){
            return dp[index][k];
        }
        // choose current
        int ans1 = 0,ans2 = 0;
        ans1 = Math.max(recursion(index + 2,k - 1, nums,dp),nums[index]);
        // no choose
        ans2 = recursion(index + 1,k,nums,dp);

        return dp[index][k] = Math.min(ans1,ans2);
    }
}
